(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Biodiversity Heritage Library | Children's Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "mit :: lcs :: tm :: MIT-LCS-TM-031"

m 



A CLASS OP PINITE COMPUTATION STRUCTURE! 
SUPPORTING THir PAST POURIER TRANSFORM 

Richard J. Bonneau 



MAC Technical Memorandum 31 
March 1 973 



Work reported here is supported in part by the Raytheon Advanced 
Decree 'Program, and by Project MAC, an. M.I.T. research program 
sponsored bv the Advanced Research Projects Agency, Department of 
Defense, under ARPA Order No. 2095 and under Office of Naval 
Research Contract Number N00014-70- A-0362-0006 and the National 
Science Foundation under contract number GJCO-43'27. 



Massachusetts Institute of Technology 

PROJECT MAC 

Cambridge Massachusetts 02139 



rr-y'i- 



SHflUTOUflTB. HOITA'IU'IMOO 3TIHn 10 2$AJD A 



oM .1. fnaifolft 



;ipfe 



rj ajjbnjrtomsM Isoiarfos? 0AM 



£V°r &rm 



»T*X*M 'iH'^aNyt . #»jfcflrt<I . t^ bos i<ist3©*5 9€»i^an 

■tim m t tfl beoaavbk sett ^ef Jtoroaabqa 

3& «£$ EO A1HA os&fw « satiated 

tf! TadmM *mtSsK& rtoommsi 

ill • te&Mtim *Wbm mk3aixw<fiL aonaioP, 




8^rS0 aJJsauriasaasM 



DAH taSiQSt: 



s^JticrssO 



PACE 2 



Section I,- Introduction 

The Fast Fourier Transform (FFT) and modular arithmetic are 
two distinct techniques which recently have been employed to 
increase the efficiency of numerous algorithms in the area of 
symbolic and algebraic manipulation. Motivated by work done on 
fast large integer multiplication by Schonhage and Strassen [11] 
and by Knuth [7], this paper analyzes the question of when these 
two techniques can be utilized concurrently. The desirability of 
the convolution property of the EFT suggests a practical 
definition for the support of an FFT, while a generalization of 
the modular rings of integers motivates a reasonable definition 
of a finite computation structure. A Finite Computation 
Structure is defined to be a commutative ring with unity, and of 
finite, — non-zero characteristic. This report first completely 
characterizes the modular rings of integers which support the FFT 
by considering the prime factorization of the modulus. This 
characterization is then extended to provide the following 
result: Theorem ; Let R be a finite computation structure of 
characteristic in. Then R will support a K-point ITT if K divides 
p-1 for each prime p dividing m. The paper then concludes with 
examples of the application of this result to the problems of 
computing products and powers of symbolic multivariate 
polynomials. 

Section 2. The Discrete Fourier Transform 



Def inition ; Let R be a commutative ring with unity, written as 
T: — K an integer > 1, and WK an element of R of order K; i.e., a 
primitive K-th root of unity. Then the DISCRETE FOURIER 
TRANSFORM (DFT) of the K-sequence (a0,a1,.. .,a(K-i;j is the K- 
sequence 

(ao,ai,...,a(K-i)) 

given by the following equations: 



a = } a V/ 1 2 0<j<K-1 (1) 

/ . i K 



2 



PAGE 3 



Definition ; Assuming the same conditions as above, and also, 
that K possesses a multiplicative inverse in R (i.e. 1/K), then 
the INVERSE DISCRETE FOURIER TRANSFORM (IDFT) of the K-sequence 
(a0,a1,... ,a(K-ljJ is the K-sequence 

(ao,ai,...,a(K-i)) 

given by the following equations: 



a = (1/K) 



/ a W 

/ - - \ • i K 



»i = Q 



0<i<K-1 (2) 



If we consider the term ai*WK**(-i*j) to be rewritten as the 
equivalenit term 

v i ai*WK**((K-i)*j) 

:/ 

then we can rewrite the above equation as 

K ■- 1. 



a = (1/K) 



} a W 
/ K-i K 

i = 



r 



(la) 



If we now define a(K) = a(0), then the inverse DFT can be 
computed from the DIT by merely "flipping" the input sequence. 
Here, flipping consists in replacing the i-th term by the (K-i)- 
th term. Thus the same computational algorithm (for the DFT) can 
be used to compute both the DFT and the IDFT. As might be 
expected from the terminology, under the right conditions, the 
two transforms are inverses of each other, and thus provide 
different representations of K-sequences. The remainder of this 
paper will be concerned with determining some of the "right" 
conditions under which the DFT can be inverted. Note, also, that 
the DFT (and the IDFT) are linear transformations from R**K to 
R**K, (where R**K is the ring of K- tuples of elements of R with 
component addition and multiplication) since the quantities 
WK**(i*j) are all "constants" for each application of the DFT. 
For more information on this approach to the phenomenon of the 
DFT, see Nicholson [10]. 

The computation of the DFT by classical techniques usually 
involved 0(K**2) operations, as the computation of each 



PAGE 4 



transformed element took K multiplications followed by K-1 
additions. However, Cooley and Tukey [5] demonstrated a 
computation scheme by which the DIT of a K-sequence could be 
computed in only 0(K log K) operations* This method has become 
known as the fast Fourier Transform (EFT). The key concept in 
the reduction of the computation time involves the fectofization 
of K. In other words, for K highly composite, the DFl|c«m be 
computed by forming sub-sequences of the original sequence, 
performing a DFT of fewer elements on them, then assembling the 
resulting sequences* The goal here is not to develop the theory 
surrounding the FFT (see Cooley-Tukey [5]) but rather to instill 
some feeling for the immense efficiency of this algorithm and 
thus to motivate the desire to find as many ways as possible in 
which it can be i nvoked* During the remainder of this paper, the 
terms DPT and FFT will he used interchangeably, as they refer to 
a computation function and a computation algorithm which 
correspond to each other. 

The particular virtue of the DFT in many applications results 
from the following: 

Definition ; Let A = (a0,a1,.. *,a(K-1)) and B = (b0,b1,.. .,t(K- 
1)) be two K-sequences in R. Then the CONVOLUTION OF A AND B, 
written A*B, is the K-sequence C = (cO,d,.* . ,c(K-l )T~where tHe 
cj are defined as follows: 

K - 1, 

c = \ a b 0<|cK-1 (3) 

2 * > i j-i T 

i = 

where bn for n < is defined as b(n+K). 

Convolution Property of the DFT : 

Let A and B be as in the preceding definition. Let A* and B* be 
the DFT's of A and B respectively. Then the following equation 
is true: 

(A*B)' = A* x B* (4) 

where $, x" means component-wise multiplication of K-sequences* In 
other words, the DFT transforms the convolution operation in R**K 
into the component-multiplication in R**K, according to the 
following commutative diagram: 



DFT x DFT 

R**K x R**K > R**K x R**K 

i 
i 

EFT J 

R**K > F**K 



A A 



Jt 



QED. 



PAGE 5 
1, 



As a result of (4), the convolution of two K-sequences can be 

computed in the following way: 

1)compute the transforms A" and B* of A and B 

respectively. 
2) perform componentwise multiplication on A** and B* 

to obtain a K-sequence C". 
3) perform the inverse DFT on C to obtain the 

convolution sequence C. 

Thus, the DPT provides a method (though not an intuitive one) for 
computing the convolution of sequences, assuming that the inversr 
DFT of step 3 is possible; i.e., if we can turn the bottom arrow 
around in the above figure* What this requirement amounts to is 
that we must able to compute a *true n inverse DFT. 

Let us now look into the requirements for the invert ibility of 
the DFT. If we apply the inverse DFT of equation 2 to the 
sequence of elements computed via the DFT of equation 1 f the 



PAGE 6 



Inasmuch as the following quantity appears quite frequently in 
- " lie ■ 

IX 



following equations ..will hold: 

As a result, the IDFT, as defined originally, will be a true 
inverse <«=> a"hat-hat sub 1" = a«sub 1" for all 1 < K-+1 <==> 

(Recall that delta(i,j) = 1 if i=j and 0. otherwise.) Notation: 
Inasmuch as the following quantity appears quite fr« 
the rest of this paper, we use the following notation: 

S. * * u 

Using this notation, wwe obtain the requirement: The IDFT is an 
inverse <=> S"sub 1" = K delta(0,l ). Thus, a reasonable basis 
upon which to build a useful DFT (i.e., one able to produce the 
convolution) is to define: 

Definition : Let K be > 1 . The Support , of a K-point DFT is a 
commutative ring R with identity such tnat 

:S1) There exists ,1/K in R. 
S?) There exists wK in R whose order = K. 
[S3) S"sub 1" s K delta(0,l) for all 1 < K-1. 

Note that the support of an ITT is an "essential" property of a 
ring ; i.e., if a ring R supports a K-point FFI and R is 
contained in a larger ring R', then R' also supports K-point 

EFT's. 

Two examples of support of a K-point EFT are thecomplex numbers 
with wK being the complex number cos(2T^K)+f-i sm(2^K), and 
also the algebraic number field Q[t1, where * is a formal 
solution to the equation x**K = 1, and'Q is the field of rational 
numbers. 



Section 3. Finite Computation Structures 

This section deals with the problem of developing a sufficiently 
rich generalization of the structure of modular rings of 



PAGE 7 



integers* The motivation for this generalization derives from 
the desire to develop data structures whose underlying arithmetic 
is precisely modular arithmetic* This will enable the modelling 
of a data structure within a computer. As a result of this 
thinking, we propose the following: 

Definition : A finite Computation Structure is a commutative ring 
with unity, having finite, non-zero characteristic • (Recall that 
the characteristic of a ring is the smallest integer m such that 
ma = for all a in the ring. See Lang [8] and Albert [1].) 

If the above definition holds, we say that R is a finite 
computation structure (fcs) of characteristic m. It can easily be 
shown that if R is an fcs of characteristic m, then there exists 
a subring S in R which is isomorphic to the integers modulo m 
(Z/mZ). Thus the finite computation structure concept 
encompasses the class of all modular rings of integers. 
Examples : 

Z/mZ for all integers m. 

(Z/mZ)[x1,x2,...,xn] for all m and all n. 

(Z/mZ)**n for all m and all n, where multiplication is 
component multiplication. 

4) (Z/mZ)**n for all m and all n, where multiplication is 
convolution of n- tuples. 

5) GE(p**n) (field of p**n elements) for all primes 
p and all integers n > 0. 



Section 4* Characterization of Modular Rings of Integers 

In order to characterize the class of finite computation 
structures vis-ar-vis the PFT, it is first necessary to consider 
the case of modular rings of integers inasmuch as one of these 
rings is embedded in every fcs. The goal of this section is to 
characterize those modular rings of integers which support a K- 
point EFT. In order to do this, we will draw upon work down by 
Pollard [11 ]• In his work, Pollard puts forth necessary 
conditions for the support of FFT's in modular rings of integers 
(Theorem A). The method of this section is to prove the converse 
of Pollard's result (Theorem B), eliminate a case untouched by 
Pollard (Theorem C), and finally, remove unneeded hypotheses from 
the resulting equivalence (Theorem D). For the proofs given in 
this section, the author assumes the reader to have basic 
understanding of elementary number theory (as in Grosswald [6]) 
and elementary group theory (as in Birkhoff and Mac-Lane [2]). 

Note: In the remainder of the paper we will use the following 
notational conveniences: 



PAGE 8 



Printed 

Pi 
ei 

pi**ei 

Zm 

Zpi**ei 

Z(m) 
Z(pi**ei) 

wK 



Theorem A: 



Written 
cPC-mj 



Pollard's theorem. 



Meaning 

p sub i, a prime number 

e sub i, a positive integer 

p sub i to the e sub i power 

The ring of integers irodulo m 

The ring of integers modulo 

the ei-th power of the prime pi 

The multiplicative group of Zm 

The multiplicative group cf Zpi**ei 

phi of m, the Euler phi-function 

K-th root of unity 



Let m be odd and 



If K divides pi-1 for every prime pi dividing m, and if there 
exists an element wK in Z(m) such that the order of wK in 
Z(pi**ei) is precisely K for all i, then the modular ring Zm will 
support a K-point EFT. 

Proof : In order to prove this result, we go back to the 

requirements for K-point FIT support* 

(SI ) Since K divides each pi-1 for all i, then K and pi are 
relatively prime for all i. This implies that K is 
relatively prime to the powers of the pi's and also to 
the product of the powers of the pi's. Hence, K is 
relatively prime to m. This implies that K possesses an 
inverse in Zm. 

(S?) Ey hypothesis, there is an element wK of order K for each 
Zpi**ei. Then, this element also has order K within Zm. 

(S3) The case for 1=0 is trivial. The proof for 1^0 depends 
heavily on: 



Lemma A: Assume the above hypothesis with 
assumption that m=p**e for some prime p. Then 
point ITT. 



the additional 
Zm supports a K- 



Proof of Lemma ; 

(51) K divides p-1 and thus, K and p are relatively prime. 

result, K has an inverse in Zp**e. 

(52) By hypothesis, there exists an element wK of order 

Zp**e. 

(53) Again, the case 1 = is trivial, so we assume 1 is 

zero. Consider nov; the expressions for S"sub 1". 
know that wK**Kl=£ M sub 1" (wK-1). Clearly, the left hand 
side of the above equation is zero as wK is a K-th root 
of unity. We need only show that S M sub 1" = (modulo 
p**e). We can do this by showing that wK-1/0 (module p) 
for then p**e would divide S"sub 1". Now, if wK = 1 



As a 

K in 

non- 

We 



PAGi: 9 



f. 



(modulo p) then (wK,p)=1 and hence wK would be an eleirent 
of the subgroup {w in Zp**e such that (w,p)=1} of 
Z(p**e). This subgroup has order p**(e-1) and Z(p**e) 
has order (p-1 )p**(e-1 )• But wK is also an eleirent of 
the cyclic subgroup of Z(p**e) of order K consisting of 
all the powers of wK. Hence, wK is a common element of 
two subgroups of Z(p**e) having relatively prime orders, 
hence the identity. Thus, wK = 1 (modulo p**e) . 
Contradiction. Thus, wK ^ 1 (modulo p) and S^sut 1" = 
(modulo p**e). 

QED for Lemma. 

To continue with the proof of the Theorem, we now let m = 
prod(pi**ei,i,1,r) where the pi are distinct primes. By lemma A, 
we know that Zpi**ei will support K-point EFT's for each i. In 
particular, S M sub 1" = (mod pi**ei) for each i. By using the 
Chinese Remainder Algorithm (see Lipson [9] for an excellent 
discussion of the various Chinese Remainder Algorithms) on the 
relatively prime moduli pi**ei, we know that S°sub 1" - (modulo 
prod(pi**ei,i,1 ,r) ) ; i.e. , (modulo m) . Thus the three 
conditions are satisfied and Zm supports K-point JTT's. 

QED. 

The next Theorem presents the converse to Theorem A and as such 
characterizes completely the odd numbers which can support K- 
point EFT's . 

Theorem B: If Zm supports K-point EFT's and m = 
prod(pi**ei,i,1,r), m odd, then K divides pi-1 for all i and 
there exists an element wK in Zm such that wK is of order K in 
Z P i**ei for all i. 

Proof : Since Zm supports K-point FFI's, then by S1, K has an 
inverse in Zm and hence K and m are relatively prime. It follows 
that K and pi are relatively prime for each i. Thus, K does not 
divide pi for all i. Next we can show that the map 

p :Zm >TTZpi**ei 

given by <Ax) = (x mod p1**e1,x mod p2**e2,.. .,x mod pr**er)) is 
a ring isomorphism and thus induces a group isomorphism between 
Z(m) and TT z (pi** ei )- first note that the order of Z(*) is 

«$c^ = <$<.Tj;-f\ e ') * -jr sup;") s£h f .-■vp^"' 

whereas the order of Z(pi**ei) is given fcy 



£tf; ") - c^.-i^i 



PAGL 10 



We know that if wK has order K in Z(m), then K must divide the 
order of Z(m). Since K does not divide any pi, then K divides 
the product prod(pi-1,i*1,r). However, we now show that K 
divides each factor pi-1. By the 3rd requirement for K-pcint FFT 
support (S3) 5 we are guaranteed that S M sub 1" = (modulo m = 
pi**ei), for all 1 < K-1 and not zero. Since the pi**ei are all 
relatively prime, "Dien S"sub l a = (modulo pi**ei) for all i. 
Now consider the order of wK in Z(pi**ei), say K1. Clearly, K1 
divides K. If K1 does not equal K then S"sub K1 M = 1+wK**K1+ 
wK**2K1+...=1 +1+1... =K (modulo pi**ei), since the order cf wK is 
K1 . But K and pi**ei are relatively prime for all pi and hence K 
^ (modulo pi**ei). We are then left with the conclusion that 
if K1 ? K, then S M sub K1" ^ (mod pi**ei), which is a 
contradiction. Thus, wK has order K in each Z(pi**ei). Thus, K 
divides the order of the group, i.e., (pi-1)pi**(ei-l). Since K 
and pi are relatively prime, then K divides pi-1 for every i. 

QED. 

Having finished categorizing completely the case of odd moduli, 
we consider now the possiblity of even moduli supporting K-pcint 
FFT's. This possibility is discarded by the following theorem. 

Theorem C ; No even modulus can support an EFT. 

Proof : We assume here that K is non-trivial; i.e., K > 1. In 
order to support a K-point FFT with a modulus m which is even, we 
must have that K possesses an inverse in Zm. This condition is 
equivalent to saying that K and m must be relatively prime and 
hence that K must be odd. If there exists an element wK in Zm of 
order K, where we now write m = prod(pi**ei,i,1,r) with p1=2, 
then by means of the isomorphism described in Theorem B, the 
order of wK in Z(2** e 1) must divide K. However, since the order 
of Z(2**e1) is 2**(e1-1), the order of wK in Z(2**e1) can only be 
even or«1. It can not oe even as it must divide K. Thus we are 
left with the fact that the order of wK in Z(2**e1) must be 1; 
i.e., wK = 1 (modulo 2**e1). In order to complete our proof we 
look at the possible cases for m: 

Case 1 : m= 2**e1 . 

In this case, wK has order 1 in Zm = Z2**ei and hence 
cannot have order K. 

Case 2: m = ml * 2**e1 where ml is odd. 

If we now invoke condition S3 for FFT support, then S f, sub 
1" must = (modulo ml * 2**e1). Since ml and 2**e1 are 
relatively prime, this implies that S*sub 1 M = (modulo 
2**e1) for all 1 < K. If we now look at S f, sub 1 w however, 
we find that S"sub 1" = 1 + wK + wK**2 + ... =1+1+1 
+ .. .. (modulo 2**e1) (since wk =i1 (modulo 2**e1)) = K 
(modulo 2**e1), which is not equal to 0, as K is odd. 



PAGE 11 



Thus, S w sub i1 M is not zero and we have a contradiction. 

Since both cases yield a contradiction, we have the result that 
even moduli cannot support FFT's. 

QED. 

The last theorem in this section combines all the results of this 
section and provides for the complete characterization of modular 
rings of integers which support the ITT. 

Theorem D: Zm supports K-point FFT's if and only if K divides 
pi-1 for every prime pi dividing m. 

Proof * Using theorems A,B and C, we see that we need only prove 

the following assertion in order to obtain the above result: 

If K divides pi-1 for all primes pi dividing m, then there exists 

an element wK in Zm of order K in each Z(pi**ei) (and hence in 

Zm). 

The argument proceeds as follows: 



1. Every Z(pi**ei) possess primitive roots^of unity; 
i.e., elements ri of order the same as Z(pi**e 
which is (pi-1)pi**(ei-1). (See Grosswald [6] 



2. The element wi defined by 

has order K in Z(pi**ei) since K divides pi-1 

and order(ri**n) = order (ri)/gcd(n, order (ri)) = K, 

where 



-C*£-)r. e <-' 



3. The element wK which is the unique solution (modulo m) 
to the following family of congruences: 

wK =.wi (modulo pi**ei) i =1,...,r 

is an element of order K in Z(pi**e}) for all i 
and thus of order K in Zm. 

Thus we see that if the hypothesis holds, we can always find an 
element of the desired order. As a result, the hypothesis of 
existence of K-th roots of unity in the equivalence implied by 
Thorems A, B and C is redundant. 

A final remark concerns the removal of the hypothesis for odd 
primes from Theorems A and B. Inasmuch as K must divide pi-1 for 
each i and that K is not 1, ther the statement that the pi must 



PAGE 12 



be odd is redundant. With the two removals of restrictions as 
described above, the equivalence of Theorems A, B and C result in 
exactly the statement of Theorem D. 

QED. 

Summary ; Utilizing the various theorems presented in this 
section, we have provided a complete characterization of modular 
rings of integers supporting the last Fourier Transforms. 

Examples : 

TZ z3~"can support only 2-point FFT's (with wK = -1). 

2. Similarly, Z3**e can only support 2-point FFT's for all e. 

3. 8-point FFT's can be performed in Zm for any m 

of the form prod((8ci+1)**ei,i,1,r) for arbitrary 
r and ci, where 8ci + 1 is prime. 
e.g., 1 7**e , 33**e ' , 1 7**e * 33**e ' . 

Section ]?: Extension to Finite Computation Structures 

As we have seen in section 4, only certain modular rings will 
support K-point FFT's. We now extend this result to include some 
of the finite computation structures. 

Theorem ; If R is a finite computation structure of 
characteristic m, then R supports a K-point FIT if K divides p-1 
for every prime p dividing m. 

Proof ; Let K divide p-1 for all primes p dividing m. Then by 
Theorem D we know that Z/mZ supports a K-point FFT. As a result, 
the requirements S1, S2 and S3 of section 2 hold in Z/mZ. Since 
R is an fcs of characteristic m, then there exists a subring S of 
R isomorphic to Z/mZ. Because all of the requirements for 
support of an FFT involve only ring operations, then any 
isomorphic copy of Z/mZ will satisfy the support requirements. 
Thus S supports K-point FFT's. However, the definition of 
support is essential and thus R also supports K-point FFT's. 

QED. 

Note; If S";Z/mZ > R is the isomorphism onto a subring of R, 

then 0"(wK) is a K-th root of unity in R. Thus, knowledge of 
modular K-th roots of unity will be sufficient to compute FFT's 
in R. 



PAGE 13 



Section 6: Applications 

The results presented have been applied to the problems of 
computing products and powers of symbolic multivariate 
polynomials over the integers (see [3] and [4]). The following 
brief example examines the application of the IFI in a finite 
computation structure to the computation of products of 
polynomials. 

Let f and g be univariate polynomials over some coefficient ring 
R, with the degree of f = m and the degree .of g = n. We csn thus 
write: 

f t*> = Q + °S* +" Q 4 * l + ' ' ' t 0^ %** 

The product polynomial h(x) = f (x)*g(x) can then be written as 

h C*N t Co ««- c,* + Ct-v* + • • • + ^H,♦K^ ,, ' +,, 
where the coefficients ,ci are computed by 

If we set K = m+n+1 and form 2 K-sequences 

A - H , *,, • ••, <U, ©, ■ ••, O) 

then the K-sequence C given by 

£ =. Ct , C,, • •• , C^, 4>1 ^ 

is precisely the convolution of A and B, as defined in Section 2. 
As a result of this observation, if the coefficient ring R 
supports K-point FFT's, the the product polynomial, h(x) can be 
computed using FFT's as follows: 

1) form the 2 K-sequences A and B 

2 j Apply a K-point FFT to each sequence, yielding A and B 

3) Multiply A and B component- wise, yielding int. 

4; Apply the inverse K-point FFT to obtain C, which is 
the sequence of coefficients of the product 
polynomial h. 
In particular, if the coefficient ring is the integer, we cannot 
perform ITT's as there are no roots of unity other than 1 and -1. 
However, if the largest coefficient (in absolute value) in A, B 
or C is bounded by M, then we can embed f(x) and g(x) in the 
polynomial ring Zm[x], where m > 2M and Zm supports K-point 



PAGE 14 



f!FT*s„ Then, the application of the 4 steps mentioned abcve will 
compute the product 

However, since the maximum coefficient is less than m/2, then 
h(x) = f(x)g(x) and we are finished* 

Similarly, if the coefficient ring R = Z[y] (i.e*: f and g are 
bivariate polynomials in x and y over the integers), we can embed 
f and g in Zm[x,y] where m is sufficiently large and Zr[y] 
supports K-point FFT s* Again, application of the 4 steps given 
above will yield a polynomial 

but since m is chosen appi^opriatdly, h(x,y) actually equals 

f(x,y)g(x,y). 

The computation of powers of polynomials proceeds in an analogous 

manner* Studies performed on these two computation©!- problems 

have indicated that the FIT methods provide significant 

improvement in the efficiency of these algorithms for a large 

class of polynomials* (See Bonneau [3] [4]). 



Section 7: Summary _ 

This paper has presented several results relating modular 
arithmetic schemes and the Fast Fourier Transform* In 
particular, the classes of modular rings of integers in which the 
FFE may he computed is completely characterized by the prime 
decomposition of the modulus* Also, an extension of this result 
for computation structures similar to modular rings of integers 
yields a sufficiency hypothesis for the computation of FFT* 

Further research in this area might be motivated by the desire to 
find necessary and sufficient conditions for FIT support in 
finite computation structures or in general rings* As an 
example, Nicholson [10], using the definition of FFT to be a 
transformation which takes "convolution-product" rings into 
"component-product" rings, provides the result that FFT's are 
supported in division rings (i*e*, rings with no zero divisors) 
iff the ring contains a particular primitive root of unity* It 
would be most desirable to extend this type of result to a larger 
class of rings* 



PAGE 1 



References 

[I] Albert* Fundamental Concepts of Higher Algebra * University 

of Chicago Press* 1956* r 

[2] Birkhoff & Mac Lane. A Survey of Modern Algebra * Third 

edition. MacMillan Co* 1 9bt> . 
[3] Bonneau. "Polynomial Multiplication and The Past Pourier 

Transform* M Department of Mathematics, Mass. Institute of 

Technology , Cambridge, Mass. 1973. (In preparation) 
[4] ^ "Polynomial Exponentiation: The Past Pourier 

Transform Revisited", Department of Mathematics, Mass. 

Institute of Technology, Cambridge, Mass* 1973* (In 

preparation) 
[5] Cooley & Tukey. "An Algorithm for the Machine Calculation of 

Complex Pourier Series." Mathematics of Computation, vol. 

19, April 1965. pp. 297-WI 

[6] Grosswald. Topics from the Theory of Numbers . Macmillan 

Company, New xork* 196b. Chapter TT 
[7] Knuth* The Art of Computer Programming — Errata et Addenda * 

Computer Science Department, Stanford University . Jan., 

1971- pp. 21-26. 
[8] Lang* Algebra * Addison-Wesley Co., Reading, Mass. 1965. 
[9] Lipson. "Chinese Remainder and Interpolation Algorithms," 

Proc . of Secon d Symposium on Symbolic Algebraic 

Manipulation , March 19717^ 
[10] Mcholson. ^Algebraic Theory of Finite Pourier Transforms* 11 

Journal of Computer and System Sciences , vol. 5» 1971. 

pp— 52 4 ~ 53F7T 

[II] Pollard. "The Past Pourier Transform in a Pinite Field." 

Mathematics of Computation , vol* 25 » number 114, April, 

>WHZ pp7 "36b - 374. 

[12] Schonhage & Strassen* "Fast Multiplication of Large 
Numbers," to appear in Computing * 



UNCLASSIFIED 



Security Classification 



DOCUMENT CONTROL DATA -R&D 

(Security classification of title, body of abstract and indexing annotation must be entered when the overall report is classified) 



1 . ORIGINATING ACTIVITY (Corporate author) 

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 
PROJECT MAC 



2fl. REPORT SECURITY CLASSIFICATION 

UNCLASSIFIED 



2b. GROUP 

NONE 



3. REPORT TITLE 



A CLASS OF FINITE COMPUTATION STRUCTURES SUPPORTING THE FAST FOURIER TRANSFORM 



4. DESCRIPTIVE NOTES (Type of report and inclusive dates) 

INTERIM SCIENTIFIC REPORT 



5- AU THOR(S) (First name, middle initial, last name) 

RICHARD J. BONNE AU 



6- REPORT DATE 

MARCH, 1973 



8a. CONTRACT OR GRANT NO. 



N00014-70-A-0362-0006 



b. PROJEC T NO. 



la. TOTAL NO. OF PAGES 



15 



7b, NO. OF REFS 

12 



9a. ORIGINATOR'S REPORT NUMBER(S) 



9b. OTHER REPORT NO(S| (Any other numbers that may be assigned 
this report) 

NONE 



10. DISTRIBUTION STATEMENT 



DISTRIBUTION OF THIS DOCUMENT IS UNLIMITED 



11. SUPPLEMENTARY NOTES 



12. SPONSORING MILITARY ACTIVITY 



OFFICE OF NAVAL RESEARCH 



13. ABSTRACT 



The Fast Fourier Transform (FFT) and modular arithmetic are two distinct 
techniques which recently have been employed to increase the efficiency of 
numerous algorithm in the area of symbolic and algebraic manipulation. 
Motivated by work done on fast large integer multiplication by Schonhage and 
Strassen [11] and by Knuth [7], this paper analyzes the question of when these 
two techniques can be utilized concurrently. The desirability of the convolution 
property of the FFT suggests a practical definition for the support of an FFT, 
while a generalization of the modular rings of integers motivates a resonable 
definition of a finite computation structure. A Finite Computation Structure 
is defined to be a commutative ring with unity, and of finite, non-zero charater- 
istic. This report first completely characterizes the modular rings of integers 
which support the FFT by considering the prime factorization of the modulus. 
This result: Theorem : Let R be a finite computation structure of characterizatioi 
m. Then R will support a K-point FFT if K divides p-1 for each prime p 
dividing m. The paper then concludes with examples of the application of this 
result to the problems of computing products and powers of symbolic multivariate 
polynomials. 



L 



DD F N°o R v M e 5 1473 

S/N 0102- 01 4- 6600 



(PAGE 1 ) 



UNCLASSIFIED 



Security Classification 



UNCLASSIFIED 



Security Classification 



K EY WORDS 



Fast Fourier Transform 

Finite Computation Structures 

Modular arithmentic 

Symbolic polynomial manipulation 



DD, F ,r..1473 back) 

'PAGE 2) 



UNCLASSIFIED 



Security Classification 









,*;W: 



MIT/LCS/TM-31 



A CLASS OF FINITE COMPUTATION 

STRUCTURES SUPPORTING THE 

FAST FOURIER TRANSFORM 



Richard J. Bonneau 



March 1973 



PUBLICATIONS DISTRIBUTION 

PROJECT MAC, ROOM 417-A 

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 

545 TECHNOLOGY SQUARE 

CAMBRIDGE, MASS. 02139 



March 1973 



We have recently issued Project MAC Technical Memorandum TM-31: 

A Class of Finite Computation Structures 
Supporting the Fast Fourier Transform 

Richard J. Bonneau 
AD 757-787 

ABSTRACT 

The Fast Fourier Transform (FFT) and modular arithmetic are two 
distinct techniques which recently have been employed to increase the 
efficiency of numerous algorithms in the area of symbolic and algebraic 
manipulation. Motivated by work done on fast large integer multiplication 
by Schonhage and Strassen [11] and by Knuth [7], this paper analyzes the 
question of when these two techniques can be utilized concurrently. The 
desirability of the convolution property of the FFT suggests a practical 
definition for the support of an FFT, while a generalization of the 
modular rings of integers motivates a reasonable definition of a finite 
computation structure* A Finite Computation Structure is defined to be a 
commutative ring with unity, and of finite, non-zero characteristic. 
This iceport first completely characterizes the modular rings of integers 
which support the FFT by considering the prime factorization of the 
modulus. This result: Theorem : Let R be a finite computation structure 
of characterization nu Then R will support a K-point FFT if K divides 
p-1 for each prime p dividing m. The paper then concludes with examples 
of the application of this result to the problems of computing products 
and powers of symbolic multivariate polynomials.